package queue.impl;

import queue.Queue;


import java.util.*;

/**
 * User: Vitalii Serdiuk
 * Date: 04.12.13 10:56
 */
public class ArrayQueue<T> implements Queue<T> {

    private static final int MIN_INITIAL_CAPACITY = 8;

    private T[] arr;
    private int head;
    private int size;

    public ArrayQueue() {
        arr = (T[]) new Object[MIN_INITIAL_CAPACITY];
    }

    public ArrayQueue(int capacity) {
        arr = (T[]) new Object[capacity];
    }

    public ArrayQueue(T[] array ,int head, int size){
        arr = array;
        this.head = head;
        this.size = size;
    }

    @Override
    public T element() {
        T e = arr[head];
        if (e != null) {
            return e;
        } else
            throw new NoSuchElementException();
    }

    @Override
    public boolean offer(T e) {
        if (e == null)
            throw new NullPointerException();
        if (size + 1 > arr.length) resize(size+1);
        arr[(head + size) % arr.length] = e;
        size++;
        return true;
    }

    @Override
    public T peek() {
        T e = arr[head];
        return e != null ? e : null;
    }

    @Override
    public T poll() {
        if (size == 0) return null;
        T x = arr[head];
        head = (head + 1) % arr.length;
        size--;
        if (arr.length >= 3 * size) trimSize();
        return x;
    }

    private void trimSize() {
        T[] arr2 = (T[]) new Object[Math.max(1, size / 3)];
        for (int i = 0; i < size; i++) {
            arr2[i] = arr[(head + i) % arr.length];
        }
        arr = arr2;
        head = 0;
    }

    @Override
    public T remove() {
        T x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

    private void resize(int minCapacity) {
        T[] arr2 = (T[]) new Object[Math.max(1, minCapacity * 3 / 2)];
        for (int i = 0; i < minCapacity; i++) {
            arr2[i] = arr[(head + i) % arr.length];
        }
        arr = arr2;
        head = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public boolean contains(Object o) {
        if (o == null)
            return false;
        int mask = arr.length - 1;
        int i = head;
        T x;
        while ((x = arr[i]) != null) {
            if (o.equals(x))
                return true;
            i = (i + 1) & mask;
        }
        return false;
    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int cursor = head;


            @Override
            public boolean hasNext() {
                int cur = getNextIndex();
                return (arr[cur] != null);
            }

            private int getNextIndex() {
                return ((cursor + 1) % (arr.length - 1));
            }

            @Override
            public T next() {
                int cur = cursor;
                cursor = getNextIndex();
                return arr[cur];
            }

            @Override
            public void remove() {
                remove0(cursor);
            }
        };

    }

    private void remove0(int index) {
        int cursor = index;
        int mask = arr.length - 1;
        if (cursor == head) poll();
        if (cursor > head) {
            for (int i = cursor; i > head; i--) {
                arr[i] = arr[i - 1];
            }
            arr[head] = null;
            head = (head + 1) & mask;
            size--;
        } else if (cursor < head) {
            int tail = (head + size) %(arr.length - 1);
            for (int i = cursor; i < tail; i++) {
                arr[i] = arr[i + 1];
            }
            arr[tail] = null;
            size--;
        }

    }

    @Override
    public Object[] toArray() {
        return copyElements(new Object[size()]);
    }

    private <T> T[] copyElements(T[] a) {
        int tail = (head + size) % (arr.length - 1);
        if (head < tail) {
            System.arraycopy(arr, head, a, 0, size());
        } else if (head > tail) {
            int headPortionLen = arr.length - head;
            System.arraycopy(arr, head, a, 0, headPortionLen);
            System.arraycopy(arr, 0, a, headPortionLen, tail);
        }
        return a;
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        return copyElements((T1[]) new Object[size()]);
    }

    @Override
    public boolean add(T t) {
        return offer(t);
    }

    @Override
    public boolean remove(Object o) {
        int h = head;
        int i = h;
        int mask = arr.length - 1;
        do {
            if (arr[i].equals(o))
                remove0(i);
            i = (i + 1) & mask;
        } while (i != h);
        return true;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        Iterator<?> e = c.iterator();
        while (e.hasNext())
            if (!contains(e.next()))
                return false;
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {

            Object[] a = c.toArray();
            int numNew = a.length;
            resize(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, arr, size, numNew);
            size += numNew;
            return numNew != 0;

    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (c.contains(e.next())) {
                e.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        Iterator<T> e = iterator();
        while (e.hasNext()) {
            if (!c.contains(e.next())) {
                e.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public void clear() {
        int h = head;
        head = 0;
        int i = h;
        int mask = arr.length - 1;
        do {
            arr[i] = null;
            i = (i + 1) & mask;
        } while (i != h);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof ArrayQueue)) return false;

        ArrayQueue that = (ArrayQueue) o;

        if (head != that.head) return false;
        if (size != that.size) return false;
        if (!Arrays.equals(arr, that.arr)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = arr != null ? Arrays.hashCode(arr) : 0;
        result = 31 * result + head;
        result = 31 * result + size;
        return result;
    }

    @Override
    public String toString() {
        return "ArrayQueue{" +
                "arr=" + Arrays.toString(arr) +
                ", head=" + head +
                ", size=" + size +
                '}';
    }
}
